package mashibing.class19;

/**
 * 规定1和A对应、2和B对应、3和C对应...26和Z对应
 * 那么一个数字字符串比如"111”就可以转化为:
 * "AAA"、"KA"和"AK"
 * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果
 */
public class Class19_2_ConvertToLetterString {

    // str只含有数字字符0~9
    // 返回多少种转化方案
    public static int number(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        return process(str.toCharArray(), 0);
    }

    private static int process(char[] str, int i) {
        if (i == str.length) {
            return 1;
        }
        if (str[i] == '0') {
            return 0;
        }
        int way = process(str, i + 1);
        if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' <= 26) {
            way += process(str, i + 2);
        }
        return way;
    }

    /**
     * dp
     */
    public static int dp(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] dp = new int[s.length() + 1];
        dp[s.length()] = 1;
        char[] str = s.toCharArray();
        for (int i = s.length() - 1; i >= 0; i--) {
            if (str[i] == '0') {
                dp[i] = 0;
                continue;
            }
            int way = dp[i + 1];
            if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' <= 26) {
                way += dp[i + 2];
            }
            dp[i] = way;
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(number("111111"));
        System.out.println(dp("111111"));
    }
}
